package cn.cxq.learning.array;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 *  剑指offer
 * 滑动窗口的最大值
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：439917
 * 本题知识点： 堆 双指针
 *  算法知识视频讲解
 * 题目描述
 * 给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
 * 窗口大于数组长度的时候，返回空
 * 示例1
 * 输入
 * 复制
 * [2,3,4,2,6,2,5,1],3
 * 返回值
 * 复制
 * [4,4,6,6,6,5]
 */

public class SlidingWindow {

    @Test
    public void testMaxInWindows() {
        System.out.println(maxInWindows(new int[]{16, 14, 12, 10, 8, 6, 4}, 5));
    }

    //看了牛客题解了之后，决定采用双端队列
//    遍历数组的每一个元素，
//    如果容器为空，则直接将当前元素加入到容器中。
//    如果容器不为空，则让当前元素和容器的最后一个元素比较，如果大于，则将容器的最后一个元素删除，然后继续讲当前元素和容器的最后一个元素比较
//    如果当前元素小于容器的最后一个元素，则直接将当前元素加入到容器的末尾
//    如果容器头部的元素已经不属于当前窗口的边界，则应该将头部元素删除
//    首先容器中放的元素应该是单调递减的。然后还有删除容器头部元素和最后一个元素的操作。因此，这样的数据结构就是双端队列。c++中就是deque
    public ArrayList<Integer> maxInWindows(int[] num, int size) {

        ArrayList<Integer> result = new ArrayList<>();

        if (num.length == 0 || size == 0 || num.length < size) {
            return result;
        }

        LinkedList<Integer> deque = new LinkedList<>();

        for (int i = 0; i < num.length; i++) {

            while (deque.size() > 0 && num[deque.getLast()] < num[i]) {
                deque.removeLast();
            }
            deque.addLast(i);

            while (deque.getFirst() <= i - size) {
                deque.removeFirst();
            }

            if (i >= size - 1) {
                result.add(num[deque.getFirst()]);
            }
        }

        return result;
    }


    //自己的拙见，使用一个linkedlist让他一直保存滑动窗口中数组递减的状态然后从中取数，结果可想而知的慢。
//    public ArrayList<Integer> maxInWindows(int [] num, int size) {
//
//        ArrayList<Integer> result = new ArrayList<>();
//
//        if (num.length == 0 || size == 0 || num.length < size) {
//            return result;
//        }
//
//        LinkedList<Integer> temp = new LinkedList<>();
//        for (int i = 0; i < size; i++) {
//            temp.add(num[i]);
//        }
//        temp.sort((value1,value2)-> value2 - value1);
//        result.add(temp.getFirst());
//        int max = temp.getFirst();
//
//        for (int i = size; i < num.length; i++) {
//
//            temp.remove(new Integer(num[i-size]));
//
//            if (num[i] >= max) {
//                temp.addFirst(num[i]);
//                result.add(num[i]);
//            } else {
//                temp.add(num[i]);
//                temp.sort((value1,value2)-> value2 - value1);
//                result.add(temp.getFirst());
//            }
//
//            max = temp.getFirst();
//        }
//        return result;
//    }
}
